#include <vector>
#include <map>
using namespace std;

class riichi // 立直判断
{
private:
    static const int SHANTENSYS = 4;

    static map<long long, int> shantenmap; // 实际上记录的是不同面子情况下搭子数量
    static int listshantenarr[9], makeshantenarr[5];

    static void makeshantenmap(int& mapval, int k = 0, int num = 0);
    static void listshantenmap(int k = 0, int num = 0);
    static int chitoishanten(const unsigned char* bu);
    static int kokushishanten(const unsigned char* bu);
    static int calcmentsu(unsigned char* bu, int mentsu);
    static int calchaisize(const unsigned char* bu);

public:
    static int calcshanten(unsigned char* bu, int fulumentsu);
};

// 声明两个静态成员变量，否则无法通过链接
map<long long, int> riichi::shantenmap;
int riichi::listshantenarr[9], riichi::makeshantenarr[5];

void riichi::makeshantenmap(int &mapval, int k, int num){
    if(k == 9){
        int dazi = 0, tarr[9];
        for(int i = 0; i < 9; i ++)
            tarr[i] = listshantenarr[i];
        for (int i = 0; i < 9; i ++ ){
            if (tarr[i] >= 2){
                tarr[i] -= 2;
                dazi ++ ;
            }
            if (i < 8 && tarr[i] > 0 && tarr[i + 1] > 0){
                tarr[i] -- ;
                tarr[i + 1] -- ;
                dazi ++ ;
            }
            if (i < 7 && tarr[i] > 0 && tarr[i + 2] > 0){
                tarr[i] -- ;
                tarr[i + 2] -- ;
                dazi ++ ;
            }
        } 
        if (makeshantenarr[num] >= 1 << (SHANTENSYS - 1) || makeshantenarr[num] < dazi){
            makeshantenarr[num] = dazi;
            mapval = 0;
            for (auto i : makeshantenarr)
                mapval = (mapval << SHANTENSYS) + i;
        }
        return;
    }
    makeshantenmap(mapval, k + 1, num);
    auto &arr = listshantenarr;
    if (arr[k] >= 3){
        arr[k] -= 3;
        makeshantenmap(mapval, k, num + 1);
        arr[k] += 3;
    }
    if (k < 7 && arr[k] && arr[k + 1] && arr[k + 2]){
        arr[k] -- ;
        arr[k + 1] -- ;
        arr[k + 2] -- ;
        makeshantenmap(mapval, k, num + 1);
        arr[k] ++ ;
        arr[k + 1] ++ ;
        arr[k + 2] ++ ;
    }
}

void riichi::listshantenmap(int k, int num){
    if (k == 9){
        for (auto &i : makeshantenarr)
            i = 1 << (SHANTENSYS - 1);
        long long index = 0;
        for (auto i : listshantenarr)
            index = (index << SHANTENSYS) + i;
        int &mapval = shantenmap[index];
        makeshantenmap(mapval);
        return;
    }
    for (int i = 0; i <= 4 && i + num <= 14; i ++ ){
        listshantenarr[k] = i;
        listshantenmap(k + 1, num + i);
    }
    listshantenarr[k] = 0;
}

int riichi::chitoishanten(const unsigned char* bu){
    int count = 6, over = 0, total = 0;
    for (int i = 0; i < 34; ++i){
        total += bu[i];
        if (bu[i] > 1){
            count -- ;
            over += bu[i] - 2;
        }
    }
    over -= (total == 14);
    return over > count ? over : count;
}

int riichi::kokushishanten(const unsigned char* bu){
    int type = 0, two = 0;
    for (unsigned i = 0; i < 34; i ++ )
        if (bu[i] && (i % 9 == 0 || i % 9 == 8 || i > 29)){
            type ++ ;
            if (bu[i] > 1) two = 1;
        }
    return 13 - type - two;
}

int riichi::calcmentsu(unsigned char* bu, int mentsu){
        int toi = 0, res = INT_MAX;
    for (int i = 27; i < 34; i ++ )
        if (bu[i] >= 3) mentsu ++ ;
        else if (bu[i] == 2) toi ++ ;
    std::vector<int> d, tvec;
    d.resize(5);
    for (auto &i : d)
        i = -100;
    d[0] = 0;
    tvec.resize(5);
    for (int i = 0; i < 27; i += 9){
        long long index = 0;
        for (int j = 0; j < 9; j ++ )
            index = (index << SHANTENSYS) + bu[i + j];
        int cint = shantenmap[index];
        for (int k = 4; k >= 0; k -- ){
            tvec[k] = cint & ((1 << SHANTENSYS) - 1);
            cint >>= SHANTENSYS;
        }
        for (int j = int(d.size()) - 1; j >= 0; j -- )
            for (int k = int(d.size() - 1) - j; k >= 0; k -- )
                if (!(tvec[k] >> (SHANTENSYS - 1)) && d[j] + tvec[k] > d[j + k])
                    d[j + k] = d[j] + tvec[k];
    }
    for (int I = 0; I < int(d.size()); I ++ ){
        int i = I + mentsu, j = toi + d[I];
        int tt = 8 - i * 2 - j;
        if (i + j > 4) tt = 4 - i;
        if (tt < res) res = tt;
    }
    return res;
}

int riichi::calchaisize(const unsigned char* bu){
    int res = 0;
    for(int i = 0; i < 34; ++i)
        res += bu[i];
    return res;
}

int riichi::calcshanten(unsigned char* bu, int fulumentsu){
    if (!shantenmap.size())
        listshantenmap();
    
    int chitoi = (fulumentsu == 0) ? chitoishanten(bu) : INT_MAX;
    int kokushi = (fulumentsu == 0) ? kokushishanten(bu) : INT_MAX ;
    int normalres = calcmentsu(bu, fulumentsu);
    for(int i = 0; i < 34; ++i)
        if (bu[i] > 1){
            bu[i] -= 2;
            int tres = calcmentsu(bu, fulumentsu) - 1;
            if (tres < normalres)
                normalres = tres;
            bu[i] += 2;
        }
    int res = normalres;

    if (chitoi < res) res = chitoi;
    if (kokushi < res) res = kokushi;
    return res;
}